import random       #用于生成随机数的功能库

''' 定义一个二叉树节点类 '''
class TreeNode(object):
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right

''' 创建一个 n 层完全二叉树 '''
def createBinaryTree(n):
    i=n-1
    queue=[]
    while i>=0:
        tmp_queue=[]
        if len(queue)==0:
            for j in range(1<<i):
                tmp_queue.append(TreeNode(random.randint(0,9)))
        else:
            for j in range(1<<i):
                left=queue.pop(0)
                right=queue.pop(0)
                tmp_queue.append(TreeNode(random.randint(0,9), left, right))
        queue = tmp_queue
        i=i-1
    return queue[0]

''' BFS '''
def BFS(root):
    if root is None:
        return []
    print("BFS")
    queue=[root]
    res=[]
    while len(queue)!=0:
        tmp_queue=[]
        tmp=[]
        while len(queue)!=0:
            node=queue.pop(0)
            tmp.append(node.val)
            if node.left is not None:
                tmp_queue.append(node.left)
            if node.right is not None:
                tmp_queue.append(node.right)
        queue=tmp_queue
        print(tmp)
        res.append(tmp)

''' 
    DFS 
    参考：https://blog.csdn.net/XTAOTWO/article/details/83625586
'''
def DFS(root):
    if root is None:
        return []
    print("DFS")
    stack=[]
    res=[]
    stack.insert(0,root)
    while len(stack)!=0:
        node=stack.pop(0)
        res.append(node.val)
        if node.right is not None:
            stack.insert(0,node.right)
        if node.left is not None:
            stack.insert(0,node.left)
    print(res)
    return res

def main():
    n=3
    root=createBinaryTree(3)
    BFS(root)
    DFS(root)

if __name__ == "__main__":
    main()


